树的直径

树的直径是一个非常经典的概念，具体定义就是一颗树上的最长链。
关于直径有一个非常常见的结论：可以通过两次$dfs$来求得树上的一条直径（直径是可以不唯一的）。首先随便选择一个点$x$往外遍历找到$x$能到达的最远点$y$，再从$y$出发往外走走到最远点$z$，则$y$到$z$的一条简单路径就是树的直径。
这个结论的证明分为两步：
$dfs$贪心时的第二步最远点显然是正确的，一定能拿到最远距离的。
第一步是证明：从树上任意一点出发走到的最远点，一定是树上直径的一个端点。
反证法：假设某个点走出去的最远点是$x$而$x$拓展出去得到的一个直径的候选项短于另外一组同样方式求的的$A$和$B$，那么无非就两种情况，第一种是两者不相交，如下图：

由于整个图是联通的，我们可以找到一个点$T$链接两个直径，如图：

根据定义：$D_{Y,K}$是比$D_{B,K}$长的，否则不会选择$y$，但是这样的话对于$A$来说，选择与$Y$连通明显更优，与他是最长的直径矛盾了，这种情况下只有当假设正确的时候，也就是两者相等都是树上的直径的时候才是正确的。
第二个是假设他俩是相交于一点Z的话，如下
显然在交于某一点Z的时候，根据最远点的定义，一定有$D_{A,Y} > D_{Z.A} > D_{Z,B}$即$D_{Z,Y}$是三者中最长的，但是这样的话，$A$点应该选择连通向$y$而不是$B$，这就矛盾了，所以第二种情况也是不成立的，因为只有在假设正确的时候，也即是两者相等都是直径的时候，才不矛盾。
综上，结论是正确的，即从树上任意一点出发走到的最远点一定是直径的一个端点。
参考代码如下：
注意这个代码只是$dfs$部分，是要跑两次的，$t$就是最终的最远点。

void dfs(int u,int& t)
{
	st[u] = 1;
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];
		if(st[v] == 1)	continue;
		dist[v] = dist[u] + cost[i];
		if(dist[v] >= dist[t])	t = v;		
		dfs(v,t);
	}
	st[u] = 0;
}

但是这种贪心做法仅能应对所有权都是正权的情况，如果图里有负权，就不能用了。
在这种情况下就得用树形DP来做了，DP的具体内容就不详细展开了，说简单一点。
首先，直径如果包含$x$节点，则一截是$x$往他的子树下伸展得到，另一截是另一个子树伸展出去得到，形成的一条链。
定义:$D[x]$为$x$节点往以$x$为根的子树下走，能走到的所有长度集合中最大的。
转移:D[x] = max{D[S] + edge(x,S)
其中$S$是$x$的一个子节点，$edge(x,S)$表示两点连边的权值。
其次，还得把另一边加上。
定义:F{x]是以$x$为中间点形成的一条链的所有长度集合里最大的。
转移:$F[x] = max(D[x] + D[S] + edge(x,S))$
注意$x$和$s$是不能相同的，不然会重复计算，因此，具体代码时要先更新$F[x]$再更新具体的距离。
参考代码如下：
这里没有明确地写出$F[]$，直接记录并修改的最大值$t$做完之后$t$就是直径。

void dp(int u,int& t)
{
	st[u] = 1;
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];
		if(st[v] == 1)	continue;
		dp(v,t);
		t = max(t,dist[u] + dist[v] + cost[i]);
		dist[u] = max(dist[u],dist[v] + cost[i]);
	}
	st[u] = 0;
}